"""
Problem 51: https://projecteuler.net/problem=51

Prime digit replacements

By replacing the 1st digit of the 2-digit number *3, it turns out that six of
the nine possible values: 13, 23, 43, 53, 73, and 83, are all prime.

By replacing the 3rd and 4th digits of 56**3 with the same digit, this 5-digit
number is the first example having seven primes among the ten generated numbers,
yielding the family: 56003, 56113, 56333, 56443, 56663, 56773, and 56993.
Consequently 56003, being the first member of this family, is the smallest prime
with this property.

Find the smallest prime which, by replacing part of the number (not necessarily
adjacent digits) with the same digit, is part of an eight prime value family.
"""

# _*_ conding:UTF-8 _*_
'''
@author = Kuperain
@email = kuperain@aliyun.com
@IDE = VSCODE Python3.8.3
@creat_time = 2022/5/16
'''


import re
N = 1000000
PrimesT = [True]*N
PrimesT[0] = False
PrimesT[1] = False
for i in range(2, N):
    for k in range(i, (N-1)//i+1):
        PrimesT[i*k] = False

Primes = [n for n in range(N) if PrimesT[n]]
PrimesTotal = len(Primes)

print(f'{PrimesTotal} primes(<{N}) are ready!')


def solution() -> int:
    '''
    n(0),n(1),n(2),n(3),n(4),n(5),n(6),n(7),n(8),n(9)

    exist 8 primes and 2 composite numbers
        #1 all numbers have same total of digits
        #2 at least 3 consecutive numbers are primes
            p1,p2,p3, p1 < p2 < p3
        #3 n(i) is an arithmetic progression
            p1 + p3 = 2 * p2
        #4 diff matchs r'^1[0|1]*0$'
        #5 in p1,p3, digits matching '1' position must be same
        #6 the same digit must <7. if =7, in the front exist p1',p2',p3'


    '''

    # If first digit of p1 be replaced,
    # prime testing 9**** may be overflow
    # e.g N=20000 13183 -> 93183, raise IndexError overflow
    # so, for N=1000, p1 with 3-digit will be safe
    #     if the result is 6-digits, N must be larger than 10^6

    for i1 in range(PrimesTotal):
        # if i1 % (PrimesTotal//100) == 0:
        #     print(f'{Primes[i1]}, runing, {i1 // (PrimesTotal//100)}%')
        p1 = Primes[i1]
        p1s = str(p1)
        lens1 = len(p1s)
        for i3 in range(i1+2, PrimesTotal):
            p3 = Primes[i3]
            p3s = str(p3)

            # 1. same length
            if len(p3s) > lens1:
                break

            # 2. at least 3 consecutive numbers are primes
            # 3. p1 + p3 = 2 * p2

            p2 = (p1+p3)//2
            if not PrimesT[p2]:
                continue

            # 4. diff matchs r'^1[0|1]*0$'
            diff = re.findall(r'^1[0|1]*0$',
                              str(p2-p1))

            if len(diff) != 1:
                continue

            # 5. same digit matching '1'

            diff = diff[0].zfill(lens1)
            digits = {p1s[i] for i in range(lens1) if diff[i] == '1'}

            # matchs = list(zip(p1s, diff))
            # digits = {pair[0] for pair in matchs if pair[1] == '1'}

            if len(digits) != 1:  # not same digit
                continue

            # 6 the same digit must <7
            if digits.pop() >= '7':
                # print(p1,'>=7')
                continue

            # final. exist 8 primes and 2 composite numbers
            nums = []

            for d in ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']:
                num = [d if diff[i] == '1' else p1s[i] for i in range(lens1)]
                nums.append(''.join(num))

            # print(nums)
            # ['00059', '11159', '22259', '33359', '44459',
            #  '55559', '66659', '77759', '88859', '99959']
            # 11159 22259 33359 11100

            if nums[0][0] == '0':
                nums = nums[1:]

            # print(nums)

            nums = [ns for ns in nums
                    if PrimesT[int(ns)]]

            if len(nums) == 8:
                return nums+[diff]


if __name__ == "__main__":
    import doctest
    doctest.testmod(verbose=False)

    print(solution())
    # ['121313', '222323', '323333', '424343',
    #  '525353', '626363', '828383', '929393',
    #  '101010']
